package org.example.myleet.p767;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 大顶堆
 * 4 ms
 * O(n)
 */
public class Solution {
    public String reorganizeString(String S) {
        LetterCount[] letterCount = new LetterCount[26];
        for (int i=0; i<26; i++) {
            letterCount[i] = new LetterCount();
            letterCount[i].letter = (char) (i + 'a');
            letterCount[i].count = 0;
        }
        for (int i=0; i<S.length(); i++) {
            ++letterCount[S.charAt(i) - 'a'].count;
        }
        char[] result = new char[S.length()];
        int ri = 0;
        while (!finish(letterCount)) {
            //每一回合重排出大顶堆（倒序）
            Arrays.sort(letterCount, new Comparator<LetterCount>() {
                @Override
                public int compare(LetterCount o1, LetterCount o2) {
                    return o2.count - o1.count;
                }
            });
            if (letterCount[0].count > 1 && letterCount[1].count < 1) {
                //频次最多的字母至少2个，但后面没有其他字母可选
                return "";
            }
            if (letterCount[1].count < 1) {
                //频次最多的字母恰好还剩1个，拼上
                result[ri++] = letterCount[0].letter;
                --letterCount[0].count;
            } else {
                //每次拼2个字母，一个频次最高的，一个频次次高的
                result[ri++] = letterCount[0].letter;
                --letterCount[0].count;
                result[ri++] = letterCount[1].letter;
                --letterCount[1].count;
            }
        }
        return new String(result);
    }

    private boolean finish(LetterCount[] letterCount) {
        for (int i=0; i<letterCount.length; i++) {
            if (letterCount[i].count > 0) {
                return false;
            }
        }
        return true;
    }

    class LetterCount {
        char letter;
        short count;

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("LetterCount{");
            sb.append("letter=").append(letter);
            sb.append(", count=").append(count);
            sb.append('}');
            return sb.toString();
        }
    }
}
